package com.axzh.interview.base;

import java.util.Arrays;

public class HeapSort {

	public static void main(String[] args) {
		int nums[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35,
				25, 53, 51 };
		System.out.println("开始排序");
		int n = nums.length;
		for (int i = 0; i < n - 1; i++) {
			// 建堆
			buildMaxHeap(nums, n - 1 - i);
			// 交换堆顶和最后一个元素
			swap(nums, 0, n - 1 - i);
			System.out.println(Arrays.toString(nums));
		}
	}


	public static void swap(int[] data, int i, int j) {
		// TODO Auto-generated method stub
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	
	public static void buildMaxHeap(int[] nums, int n) {
		int last = n;
		for(int i = (last-1)/2;i>=0;i--) {
			int j=i;
			while(j*2+1<=last) {
				int max = 2*j+1; //初始最大节点为左孩子节点
				if(max+1<=last && nums[max]<nums[max+1]) { //如果右节点存在，且右节点的值大于左节点，则把右节点赋予max
					max++;
				}
				if(nums[j]<nums[max]) { 
					swap(nums, j, max);
					j=max;
				} else {
					break;
				}
			}
		}
	}

}